package src.leetcode.hot.mid_0079;

/**
 * @author liyizzz
 * @description 单词搜索
 * @date 2024/12/10 15:51
 */
public class exist {
    public static void main(String[] args) {
        char[][] board = {{'A','B','C','E'},
                        {'S','F','E','S'},
                        {'A','D','E','E'}};
        String word = "ABCESEEEFS";
        System.out.println(new Solution().exist(board, word));
    }
}


class Solution {
    char[][] board;
    boolean[][] isused;
    boolean[][][] mamery;
    int[][] next = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    String word;
    int n;
    int m;
    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.word = word;
        n = board.length;
        m = board[0].length;
        mamery = new boolean [n][m][word.length()];
        isused = new boolean [n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == word.charAt(0)) {
                    isused[i][j] = true;
                    if(dfs(i, j, 0)) {
                        return true;
                    }
                    isused[i][j] = false;
                }
            }
        }
        return false;
    }

    private boolean dfs(int x, int y, int index) {
        if (index == word.length() - 1) return true;
//        if (mamery[x][y][index]) return false;
        mamery[x][y][index] = true;
        for (int i = 0; i < 4; i++) {
            int tx = x + next[i][0];
            int ty = y + next[i][1];
            if (tx < 0 || tx >= n || ty < 0 || ty >= m || isused[tx][ty]) continue;
            if (board[tx][ty] == word.charAt(index + 1)) {
                isused[tx][ty] = true;
                if (dfs(tx, ty, index + 1)) {
                    return true;
                }
                isused[tx][ty] = false;
            }
        }
        return false;
    }
}